The present invention relates to allocating resources in general, and more particularly, to allocating various data, signal, and/or communications processing resources.
In certain environments, data, signal, and communication processing resources may be dedicated for use by particular hardware elements, software elements (e.g., application programs), and human operators, each of which may be generally viewed as a xe2x80x9cresource user.xe2x80x9d While such resource dedication is convenient and also ensures that the necessary or otherwise appropriate resources are available whenever the resource user requests them, this one-to-one, dedicated relationship between a resource and a resource user is inefficient. This inefficiency is primarily due to the fact that dedicated resources are most often underutilized since the resource user typically uses its dedicated resource less than 100% of the time.
The present invention employs a more efficient resource allocation approach in which resources are pooled and allocated on an xe2x80x9cas neededxe2x80x9d basis. In other words, in response to a resource request, a resource (if available) is xe2x80x9cwithdrawnxe2x80x9d from a pool of resources and provided to the requesting resource user. When the resource user is finished using that resource, it is returned to the resource pool. Efficiency is increased because (1) the number of resource users may be considerably larger than the number of resources in the pool and (2) resources are removed from the pool only when they are actually used.
In order for a pooled resource system to work smoothly, the allocation and return of resources from and to the resource pool needs to be managed in an effective and efficient manner. Efficient management is more challenging when the pool of resources as well as the resource requests are not all the same. For instance, one resource request may be for a relatively small resource while another resource request might be for a relatively large resource. Moreover, resource requests may also differ in parameters other than size.
The present invention resolves these issues in part by imposing a structure on the resource pool including specific rules regarding how resources are to be allocated from the pool. Those rules may vary depending on the end application that requests and uses the resources. One example (but non-limiting) structure is the resource hierarchy shown in FIG. 1. The hierarchy includes a plurality of levels or tiers with each level having plural nodes representing a resource block at that level. The data structure is organized in such a way that it xe2x80x9cmirrorsxe2x80x9d the physical resources in terms of how those physical resources are linked or grouped. The physical resources are configured, reconfigured, allocated, de-allocated, organized, and re-organized using the data structure.
In general, a number of lower level resource units are grouped to form a corresponding, higher level resource unit. Level 1 resource blocks correspond as shown in FIG. 1 to one data processing resource unit, where a resource unit may comprise hardware and/or software. Each level 2 resource block corresponds to a group (in this example two) of consecutive level 1 resource blocks. Similarly, each level 3 resource block of the resource hierarchy corresponds to a group of consecutive level 2 resource blocks.
Thus, if a resource request requires four data processing resource units, a single level 3 resource block would be allocated to that request. A level 3 resource block corresponds, in this example, to two level 2 resource blocks which in turn corresponds to four level 1 resource blocks equivalent to the four data processing resource units.
While resources may be allocated from and returned to such a hierarchical structure in random fashion, such an approach may ultimately lead to inefficiencies. In particular, the initial, ordered structure of the resource hierarchy may become fragmented after several resource block allocations and returns. Unfortunately, because of the fragmentation, resource blocks at certain levels cannot be filly utilized. For example, FIG. 2 shows the resource hierarchy of FIG. 1 with a fragmented resource allocation configuration. Circled resource blocks correspond to a currently allocated resource block, and a square enclosing a resource block represents a currently-available resource block. Because level 1 resource block 14 is currently allocated, level 2 resource block 16, logically linked to both level 1 resource blocks 14 and 15, cannot be allocated. A xe2x80x9cdomino effectxe2x80x9d occursxe2x80x94since level 3 resource block 17 is linked to resource blocks 16 and 18, level 3 resource block 17 cannot be currently allocated even if level 2 resource block 18 were currently available.
On the other hand, if the currently-allocated resource block 19 had been allocated from currently-available resource block 15, the level resource block 18 would have been available for allocation. Similarly, if currently-allocated, level 1 resource block 21 was not allocated, and instead the currently-available level 1 resource block 23 was assigned to the resource request, the currently-unavailable level 2 resource block 21 would be available. The level 2 resource block 21 could then be combined with the level 2 resource block 25 to make available the level 3 resource block 26. Accordingly, as a result of fragmented/inefficient resource allocation at lower levels in the hierarchy, it may be difficult to provide a higher level resource block to a resource request even though there are sufficient, available resources in the resource pool to accommodate the higher level resource request.
In a pooled resource system where resources are allocated according to a particular strategy, different types or groups of pooled resources will likely have different resource allocation structures or algorithms. If more than one type of resource is required to satisfy individual service requests, coordinating the allocation of both types of resources using two or more resource structures and/or algorithms becomes complicated and inefficient.
Consider the following example in a Code Division Multiple Access (CDMA) communications system. In order for a user to transmit information, the user must be allocated a spreading code (a software resource) corresponding to a particular channel capacity. Certain spreading codes have a smaller capacity. Other spreading codes in a spreading code resource hierarchy or tree may correspond to plural ones of smaller spreading code resources. As a result, a higher capacity, spreading code parent can only be allocated if its corresponding lower capacity, spreading code children are all available. If one of those spreading code children is already allocated, the higher capacity channel spreading code parent cannot be allocated.
In addition to a software spreading code resource, a user must be allocated the necessary hardware resource to physically perform the communication. An example of such hardware includes Digital Signal Processing (DSP) and/or radio transceiver circuitry. For example, a lowest capacity channel might use only one DSP and/or transceiver hardware unit. On the other hand, a higher capacity channel may require more than one DSP and/or transceiver hardware unit. Similarly, the higher capacity parent can only be allocated if all its supporting children are available. The fact that two different resource hierarchies, (i.e., software and hardware resources) in the above example, must be navigated makes the provision of an appropriate capacity spreading code with appropriate capacity hardware resources particularly cumbersome and inefficient. Not only are two resource allocation strategies required for each pool of resources, there is no guarantee that just because a suitable resource is available from one pool that a corresponding and necessary resource from the other pool is also available.
It is an object of the present invention to overcome inefficiency by providing a resource pool structure including a data structure reflecting the free resources in the pool and that permits organized and efficient but still flexible allocation and de-allocation of resources.
It is a further object of the present invention to ensure that resource units are evenly utilized in a resource pool.
It is another object of the present invention to selectively re-allocate resources among the resource users to free other resources that can be used to form higher level resource blocks in order to meet a particular resource demand or to simply make available higher level resource blocks.
It is another object of the present invention to determine and implement a resource pool structure data structure, mirroring the free resources in the resource pool, that best suits current resource demands.
It is yet another object of the present invention to ensure that different types of resource units, e.g., hardware resources and software resources, are cooperatively allocated in response to resource requests in an efficient and effective manner.
The present invention configures a pool of resource units using a logical structure that includes first level and second level resource blocks. The terms xe2x80x9cconfigure resourcesxe2x80x9d or xe2x80x9cconfiguration of resourcesxe2x80x9d refer to a data structure which is organized to reflect or represent actual or physical resources. However, the actual resources themselves are not necessarily configured in a resource hierarchy like that shown in FIG. 1. Each first level resource block corresponds to an individual resource unit, where an individual resource unit is the smallest resource that a resource handler allocates from the resource pool. The first level resource blocks are provided in groups that form a lowest level of the resource pool structure. Each second level resource block corresponds to one of the groups of the first level resource blocks. For example, two first level resource blocks form a first level resource block group logically linked to a second level resource block. The second level resource blocks are provided in groups and form a next higher level of the resource pool structure.
Resources are allocated from the resource unit pool in an efficient manner. For example, if a request is made for a first level resource block, an available first level resource block is allocated from a partially-allocated, first level resource group where one or more first level resource blocks are currently already allocated. If a first resource block is not available, then an available first level resource block is created. In this case, a second level resource block is converted into a corresponding group of first level resource blocks, and one of the converted, first level resource blocks is then allocated to the request. A similar procedure is used at a next higher level, i.e., at third level resource blocks and groupings. In other words, if a first resource block is not available at the first level and cannot be obtained by conversion of a resource block at the second level, a third level resource block is converted into a corresponding group of second level resource blocks; a converted second level resource block is converted into a corresponding group of first level resource blocks; and one of the converted first level resource blocks is allocated.
Resource blocks are also restored to the resource unit pool structure efficiently. For example, a returned first level resource block is restored to a partially-allocated, first level resource block grouping. If that returned block completes that grouping, a new, second level resource block is made available. In one preferred embodiment, when a resource block is restored, the physical resource is restored to the same position in the resource array as from where it was originally allocated. However, the corresponding resource block in the data structure is placed last in a list of free resource blocks. This ensures that each of the physical resources in the pool is used about the same amount over time.
The resource pool is managed by a resource handler which stores in memory a data structure that mirrors the current status (free or occupied) of the resources in the resource pool. The resource pool structure represents and maintains the logical relation between resource units/blocks. For example, the data structure may include multiple lists, each list corresponding to a resource block level and each record/entry in the list representing one free resource unit. The list does not include allocated resource units.
To properly manage the resource unit pool or to otherwise meet a particular a resource request/demand, a resource handler may re-allocate resource units by moving a resource user from one resource block to another at that same level in order to create additional resource blocks at the next higher level. The resource handler may also receive traffic statistics about the number of requests for different level resource blocks collected by a statistics analyzer and determine which level in the resource unit pool structure receives the greatest number of requests, i.e., the most popular level. In an example communication system, assume the system capacity is eight voice calls or two data calls. Most of the calls in the system during busy hours are voice calls. During busy hours, if the whole system capacity is allocated for data calls, no voice calls can be made resulting in an insufficient subscriber service level in the area. By restricting the use of the transmission capacity, at least a minimum level of service for data calls and voice calls can be assured. The resource handler then re-allocates resource units in the current resource pool configuration to create additional resource blocks at the most popular level.
The present invention also cooperatively allocates different types of resource units in response to a resource request in an efficient and effective manner. An example of different types of resource units that may be cooperatively allocated include software resources and hardware resource units. A first data structure may be configured to correspond to a first pool of a first type of resource unit, e.g., software resource units. A second data structure may be configured to correspond to a second pool of a second type of resource unit, e.g., hardware resource units. A relationship is established between resource units in the first and second resource unit pools so that if one of the first resource units is available for allocation, a corresponding second resource unit is also assured available. Then when a request is received for a resource, one or more available resource units from both the first and second resource pools may be allocated using the established relationship.
The established relationship between two resource pools may be implemented, for example, using a mapping mechanism such as a matrix, where each row in the matrix represents different resource units of the first type and each column represents different resource units of the second type. Selection of a row corresponding to a resource unit of a first type automatically selects a corresponding resource unit of the second type associated with an activated column in the matrix. For a one-to-one type example relationship, the matrix is configured so that each row actively intersects with only one of the columns. The mapping relationship can be reconfigured by changing which row-column intersections are active.
Using the established relationship, only one resource selection algorithm is employed which simplifies resource allocation procedures involving more than one pool of resource units. Thus, the use of two or more separate resource selection algorithms is avoided. The need for xe2x80x9csynchronizingxe2x80x9d separate resource algorithms is also avoided. In other words, without the present invention, failure to synchronize plural resource selection algorithms leads to situations (not encountered in the present invention) where an available resource unit in one pool is allocated without a corresponding and necessary resource unit from another pool being available, e.g., as a result of different fragmentations resulting from previously allocated resources.
The present invention has particularly advantageous application to communications systems, and in particular, to radio communications systems. A preferred example embodiment of the present invention is disclosed in the context of a wide band, code division multiple access (WCDMA), spread spectrum, radio communications system. In the context of a W-CDMA radio communications system, the first pool of resource units may correspond to W-CDMA spreading codes (software type resource units), and a second pool of resource units may correspond to data processing and transceiver units (hardware resource units). Of course, as evident from the above description, the present invention has general applicability and is not limited to communications environments. Various features and advantages of the present invention, some of which have been described above, will be disclosed in further detail in conjunction with the drawings and detailed description.